#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;


//  Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
 
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        if(head==NULL){
            return NULL;
        }
        ListNode* curr = head;
        ListNode* headLess = NULL;
        ListNode* endLess = NULL;
        ListNode* headMore = NULL;
        ListNode* endMore = NULL;
        while (curr!=NULL)
        {
            if(curr->val<x){
                if(headLess == NULL){
                    headLess = curr;
                    endLess = curr;
                    curr = curr->next;
                    headLess->next = NULL;
                    endLess->next = NULL;
                }
                else{
                    endLess->next = curr;
                    endLess = endLess->next;
                    curr = curr->next;
                    endLess->next = NULL;
                }
            }
            else{
                if(headMore==NULL){
                    headMore = curr;
                    endMore = curr;
                    curr = curr->next;
                    headMore->next = NULL;
                    endMore->next = NULL;
                }
                else{
                    endMore->next = curr;
                    endMore = endMore->next;
                    curr = curr->next;
                    endMore->next = NULL;
                }
            }
        }
        if(headLess!=NULL){
            endLess->next = headMore;
            return headLess;
        }
        else{
            return headMore;
        }
        
    }
};

int main(){
    Solution S;
    ListNode* head = new ListNode(1);
    head->next = new ListNode(4);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(2);
    head->next->next->next->next = new ListNode(5);
    head->next->next->next->next->next = new ListNode(2);
    ListNode* result = S.partition(head,3);
    return 0;
}